package Algorithm.Greedy;

public class Code04_StringCross {

    public static boolean isCross1(String s1, String s2, String ai){
        if (s1 == null || s2 == null || ai == null){
            return false;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        char[] aim = ai.toCharArray();
        if (aim.length != str1.length + str2.length){
            return false;
        }
        boolean[][] dp = new boolean[str1.length + 1][str2.length + 1];
        dp[0][0] = true;
        for (int i = 1; i <= str1.length; i++){
            if (str1[i - 1] != aim[i - 1]){
                break;
            }
            dp[i][0] = true;
        }
        for (int j = 1; j <= str2.length; j++){
            if (str2[j - 1] != aim[j - 1]){
                break;
            }
            dp[0][j] = true;
        }
        for (int i = 1; i <= str1.length; i++){
            for (int j = 1; j <= str2.length; j++){
                if ((str1[i - 1] == aim[i + j - 1] && dp[i - 1][j])
                        || str2[j - 1] == aim[i + j - 1] && dp[i][j - 1]){
                    dp[i][j] = true;
                }
            }
        }
        return dp[str1.length][str2.length];
    }

    public static void main(String[] args){
        String str1 = "1234";
        String str2 = "abcd";
        String aim = "1a23bcd4";
        System.out.println(isCross1(str1, str2, aim));
    }
}
